package com.explorati.LeetCode24.swapparis;

/**
 * 24. swapParis 两两交换链表中的节点 (20')
 * 
 * 在链表中穿针引线，注意指针为空的异常
 * 
 * @author explorati
 *
 */
public class Solution {
	public static class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
		}
	}

	public ListNode swapPairs(ListNode head) {
		ListNode dummyHead = new ListNode(-1);
		dummyHead.next = head;
		if (dummyHead.next == null || dummyHead.next.next == null) {
			return dummyHead.next;
		}

		ListNode pre = dummyHead;
		ListNode cur = dummyHead.next;
		ListNode next = dummyHead.next.next;

		while (cur != null && next != null) {
			//迭代解法: 不设立头结点无解(由于head会变化)  必须设立头结点
			//如果 当前节点pre和当前节点的下一个节点cur 不为空 和 当前节点的下一个节点的下一个节点next都不为空
			//pre.next = cur.next; cur.next = pre
			cur.next = next.next;
			next.next = cur;
			pre.next = next;
			pre = cur;
			if (pre.next == null) {
				break;
			} else {
				cur = cur.next;
			}
			if (cur.next == null) {
				break;
			} else {
				next = pre.next.next;
			}

		}

		return dummyHead.next;

	}
	public static void main(String[] args) {
		ListNode head = new ListNode(1);
		head.next = new ListNode(2);
		head.next.next = new ListNode(3);
		head.next.next.next = new ListNode(4);

		new Solution().swapPairs(head);
	}
}
